package com.lsa.letcode.the40.combinationSum2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> combinationSum2(int[] num, int target) {
    	List<List<Integer>> sols = new ArrayList<>();
    	
    	if (target != 0) {
    		Arrays.sort(num);
    		boolean[] state = new boolean[num.length];
    		combine(0, num, state, target, sols);
    	}
    	
    	return sols;
    }
    
    private void combine(int i, int[] candidates, boolean[] use, int target, List<List<Integer>> sols) {
    	@SuppressWarnings("unused")
		boolean isSol = false;
    	if (target == 0) {
    		List<Integer> sol = new ArrayList<Integer>();
    		for (int j = 0; j < use.length; j++) {
    			if (use[j]) {
    				sol.add(candidates[j]);
    			}
			}
    		sols.add(sol);
    		isSol = true;
    	}
    	else if (i == candidates.length || target < 0) {
    		return;
    	}
    	else {
    		// take
    		use[i] = true;
    		combine(i + 1, candidates, use, target - candidates[i], sols);
    		
    		//not take
    		int j = i;
    		for (; j < candidates.length; j++) {
				if (candidates[j] != candidates[i]) {
					break;
				}
				else {
					use[j] = false;
				}
			}
    		combine(j, candidates, use, target, sols);
    	}
//    	printState(i, candidates, use, target, sols, isSol);
    }
}